package 算法模板;

import java.util.Arrays;

/**
 * 定义：
 * 归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法
 * 是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合
 * 并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个
 * 有序表合并成一个有序表，称为二路归并。
 * <p>
 * 思路：
 * 第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
 * 第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
 * 第三步：小的元素放入到合并空间，并移动指针到下一位置
 * 重复步骤3直到某一指针超出序列尾
 * 将另一序列剩下的所有元素直接复制到合并序列尾
 * <p>
 * 来源：百度百科
 */
public class 归并排序 {

    public static void main(String[] args) {

        int[] nums = {4, 3, 2, 6, -1, 2, 4, 55, 1};
        iterationMergeSort(nums);
        System.out.println(Arrays.toString(nums));

    }

    /**
     * TODO 递归？？？
     *
     * @param arr
     */
    public static void mergeSort(int[] arr) {
        int[] temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        sort(arr, 0, arr.length - 1, temp);
    }

    private static void sort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            sort(arr, left, mid, temp);//左边归并排序，使得左子序列有序
            sort(arr, mid + 1, right, temp);//右边归并排序，使得右子序列有序
            merge(arr, left, mid, right, temp);//将两个有序子数组合并操作
        }
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;//左序列指针
        int j = mid + 1;//右序列指针
        int t = 0;//临时数组指针
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[t++] = arr[i++];
            } else {
                temp[t++] = arr[j++];
            }
        }
        while (i <= mid) {//将左边剩余元素填充进temp中
            temp[t++] = arr[i++];
        }
        while (j <= right) {//将右序列剩余元素填充进temp中
            temp[t++] = arr[j++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while (left <= right) {
            arr[left++] = temp[t++];
        }
    }

    /**
     * 迭代
     */
    public static void iterationMergeSort(int[] nums) {

        int len = nums.length;
        //临时数组
        int[] temp = new int[len];
        int t = 0;
        //一块有多少个元素
        for (int block = 1; block < len; block = block * 2) {
            //每次需要有两块来进行排序
            for (int start = 0; start < len; start = start + block * 2) {
                int left = start;
                int mid = (start + block) < len ? start + block : len;
                int right = (mid + block) < len ? mid + block : len;

                int start1 = left, end1 = mid;
                int start2 = mid, end2 = right;
                //索引从0开始，不能包含最后一位，
                //block=1
                //第一个开始排序的区间0+1+1，实际上是索引0和1进行比较
                //第二个排序的区间2+1+1，实际上是索引2和3进行比较
                while (start1 < end1 && start2 < end2) {
                    if (nums[start1] < nums[start2]) {  //块中比较小的元素的指针向后移一位
                        temp[t++] = nums[start1++];
                    } else {
                        temp[t++] = nums[start2++];
                    }
                }
                //start2全部比较完毕，将start1剩下的元素全部put进临时数组
                while (start1 < end1) {
                    temp[t++] = nums[start1++];
                }
                //start1全部比较完毕，将start2剩下的元素全部put进临时数组
                while (start2 < end2) {
                    temp[t++] = nums[start2++];
                }
                //从第一个元素开始遍历
                t = 0;
                //将临时数组中排序好的元素替换到原数组中
                while (left < right) {
                    nums[left++] = temp[t++];
                }
                //每次存储在临时数组的元素都从0开始
                t = 0;
            }
        }
    }

}
